/*
 * @Author: your name
 * @Date: 2021-10-12 17:41:34
 * @LastEditTime: 2021-10-12 18:45:33
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: \luogu\动态规划\模板问题\P1048 采药\main.cpp
 */
#include<iostream>
using namespace std;
#include<algorithm>

const int N = 105;
const int T = 1005;

int a[N],t[N];

int f[N][T];

int main(){
    int all_n,all_t;
    cin >> all_t >> all_n;
    for(int i=1; i<=all_n; i++){
        int st,sv;
        cin >> st >> sv;
        a[i] = st;
        t[i] = sv;
    }
    for(int i=1; i<=all_n; i++){
        for(int j=0; j<=all_t; j++){
            f[i][j] = f[i-1][j];
            if(j >= a[i]){
                f[i][j] = max(f[i-1][j],f[i-1][j-a[i]]+t[i]);
            }
        }
    }
    cout << f[all_n][all_t] << endl;
    return 0;
}
